package com.搜索和回溯;

class Solution11 {
    //法一：迭代法
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        while (root!=null){
//            if(root.val<p.val && root.val<q.val) root=root.right;
//            else if(root.val>p.val && root.val>q.val) root=root.left;
//            else break;
//        }
//        return root;
//    }




//    //法一优化：迭代法
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(p.val>q.val){
//            TreeNode tmp;
//            tmp=p;
//            p=q;
//            q=tmp;
//        }
//        while (root!=null){
//            if(root.val<p.val) root=root.right;
//            else if(root.val>q.val) root=root.left;
//            else break;
//        }
//        return root;
//    }

    //递归法
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        //终止条件
        if(root==null) return null;
        //递推
        if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right,p,q);
        if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left,p,q);
        return root;
    }
}

public class 剑指Offer68二叉搜索树的最近公共祖先 {
    public static void main(String[] args) {

    }
}
